package cxydmmszl.chapter04.t063;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

/**
 * <li style="color: red;">Prob</li>
 * 信封嵌套问题
 * <li style="color: red;">Desc</li>
 * 给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B，
 * 那么信封A可以放到信封 B 里，请求出信封最多可以嵌套多少层。<br/><br/>
 * <p>
 * 输入描述：<br/>
 * 输出包含多行，第一行包括一个整数，代表信封的个数 n(1≤n≤10^5)。
 * 接下来 n 行，每行两个整数 l[i] 和 w[i]，代表信封的长度和宽度，且 −1e9≤l[i],w[i]≤1e9。<br/><br/>
 * <p>
 * 输出描述：<br/>
 * 输出包括一行，代表信封最多嵌套多少层。
 * <li style="color: red;">Link</li> CD29
 *
 * @author habitplus
 * @since 2021-09-03 15:13
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[][] arr = new int[n][2];
        String[] t;
        for (int i = 0; i < n; i++) {
            t = bf.readLine().split(" ");
            arr[i][0] = Integer.parseInt(t[0]);
            arr[i][1] = Integer.parseInt(t[1]);
        }
        bf.close();

        int ans = maxNumOfNestedEnvelop(arr);
        System.out.println(ans);
    }

    private static int maxNumOfNestedEnvelop(int[][] envelopes) {
        if (envelopes == null || envelopes.length < 1 || envelopes[0].length == 0) {
            return 0;
        }

        // 先排序，以信封的长度为第一排序关键字升序，宽度为次关键字降序
        Arrays.sort(envelopes, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]);
        int n = envelopes.length;
        int[] ends = new int[n];
        ends[0] = envelopes[0][1];

        int right = 0;
        int l, r, m;
        for (int i = 1; i < n; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (envelopes[i][1] > ends[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);
            ends[l] = envelopes[i][1];
        }

        return right + 1;
    }
}
